AustralieFrV1, Main, Exploration, bibRecord, 007314

Cover Array String Reconstruction

Identifieur interne : 007314 ( Main/Exploration ); précédent : 007313; suivant : 007315

Cover Array String Reconstruction

Auteurs : Maxime Crochemore [Royaume-Uni, France] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Solon P. Pissis [Royaume-Uni] ; German Tischler [Royaume-Uni]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2010.

RBID : ISTEX:6FFE9D108EB5131A31FE0739DB1B421A603BECA1

English descriptors

KwdEn :
- Algorithm, Algorithm minarraytostring, Algorithm prune, Alphabet, Array, Array string reconstruction, Binary alphabet, Border array, Cambridge university press, Computer science, Constructive algorithm, Data structures, Important values, Input array, Integer array, Linear runtime, Linear time, Maximal, Maximal construction problem, Maximal ratio, Maximal validity problem, Minarraytostring, Next step, Nonzero values, Output string, Proper factor, Runtime algorithm, String inference, Theoretical aspects, Unbounded alphabet, Valid array.
Teeft :
- Algorithm, Algorithm minarraytostring, Algorithm prune, Alphabet, Array, Array string reconstruction, Binary alphabet, Border array, Cambridge university press, Computer science, Constructive algorithm, Data structures, Important values, Input array, Integer array, Linear runtime, Linear time, Maximal, Maximal construction problem, Maximal ratio, Maximal validity problem, Minarraytostring, Next step, Nonzero values, Output string, Proper factor, Runtime algorithm, String inference, Theoretical aspects, Unbounded alphabet, Valid array.

Abstract

Abstract: A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array ${\mathit{C}}$ is the minimal-cover (resp. maximal-cover) array of y if ${\mathit{C}}[i]$ is the minimal (resp. maximal) length of covers of $y[0{\ldotp\ldotp}i]$ , or zero if no cover exists. In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.

Url:

https://api.istex.fr/document/6FFE9D108EB5131A31FE0739DB1B421A603BECA1/fulltext/pdf

DOI: 10.1007/978-3-642-13509-5_23

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Istex, to step Corpus: 001505
to stream Istex, to step Curation: 001505
to stream Istex, to step Checkpoint: 000C31
to stream Main, to step Merge: 007850
to stream Main, to step Curation: 007314

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Cover Array String Reconstruction</title>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
</author>
<author><name sortKey="Tischler, German" sort="Tischler, German" uniqKey="Tischler G" first="German" last="Tischler">German Tischler</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:6FFE9D108EB5131A31FE0739DB1B421A603BECA1</idno>
<date when="2010" year="2010">2010</date>
<idno type="doi">10.1007/978-3-642-13509-5_23</idno>
<idno type="url">https://api.istex.fr/document/6FFE9D108EB5131A31FE0739DB1B421A603BECA1/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001505</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001505</idno>
<idno type="wicri:Area/Istex/Curation">001505</idno>
<idno type="wicri:Area/Istex/Checkpoint">000C31</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000C31</idno>
<idno type="wicri:doubleKey">0302-9743:2010:Crochemore M:cover:array:string</idno>
<idno type="wicri:Area/Main/Merge">007850</idno>
<idno type="wicri:Area/Main/Curation">007314</idno>
<idno type="wicri:Area/Main/Exploration">007314</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Cover Array String Reconstruction</title>
<author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Computer Science, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>Université Paris-Est</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Computer Science, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country xml:lang="fr">Australie</country>
<wicri:regionArea>Digital Ecosystems & Business Intelligence Institute, Curtin University, GPO Box U1987, 6845, Perth, WA</wicri:regionArea>
<wicri:noRegion>WA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Computer Science, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
<author><name sortKey="Tischler, German" sort="Tischler, German" uniqKey="Tischler G" first="German" last="Tischler">German Tischler</name>
<affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country>
<wicri:regionArea>Dept. of Computer Science, King’s College London, WC2R 2LS, London</wicri:regionArea>
<placeName><settlement type="city">Londres</settlement>
<region type="country">Angleterre</region>
<region type="région" nuts="1">Grand Londres</region>
</placeName>
</affiliation>
<affiliation></affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2010</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Algorithm minarraytostring</term>
<term>Algorithm prune</term>
<term>Alphabet</term>
<term>Array</term>
<term>Array string reconstruction</term>
<term>Binary alphabet</term>
<term>Border array</term>
<term>Cambridge university press</term>
<term>Computer science</term>
<term>Constructive algorithm</term>
<term>Data structures</term>
<term>Important values</term>
<term>Input array</term>
<term>Integer array</term>
<term>Linear runtime</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal construction problem</term>
<term>Maximal ratio</term>
<term>Maximal validity problem</term>
<term>Minarraytostring</term>
<term>Next step</term>
<term>Nonzero values</term>
<term>Output string</term>
<term>Proper factor</term>
<term>Runtime algorithm</term>
<term>String inference</term>
<term>Theoretical aspects</term>
<term>Unbounded alphabet</term>
<term>Valid array</term>
</keywords>
<keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term>
<term>Algorithm minarraytostring</term>
<term>Algorithm prune</term>
<term>Alphabet</term>
<term>Array</term>
<term>Array string reconstruction</term>
<term>Binary alphabet</term>
<term>Border array</term>
<term>Cambridge university press</term>
<term>Computer science</term>
<term>Constructive algorithm</term>
<term>Data structures</term>
<term>Important values</term>
<term>Input array</term>
<term>Integer array</term>
<term>Linear runtime</term>
<term>Linear time</term>
<term>Maximal</term>
<term>Maximal construction problem</term>
<term>Maximal ratio</term>
<term>Maximal validity problem</term>
<term>Minarraytostring</term>
<term>Next step</term>
<term>Nonzero values</term>
<term>Output string</term>
<term>Proper factor</term>
<term>Runtime algorithm</term>
<term>String inference</term>
<term>Theoretical aspects</term>
<term>Unbounded alphabet</term>
<term>Valid array</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: A proper factor u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array ${\mathit{C}}$ is the minimal-cover (resp. maximal-cover) array of y if ${\mathit{C}}[i]$ is the minimal (resp. maximal) length of covers of $y[0{\ldotp\ldotp}i]$ , or zero if no cover exists. In this paper, we present a constructive algorithm checking the validity of an array as a minimal-cover or maximal-cover array of some string. When the array is valid, the algorithm produces a string over an unbounded alphabet whose cover array is the input array. All algorithms run in linear time due to an interesting combinatorial property of cover arrays: the sum of important values in a cover array is bounded by twice the length of the string.</div>
</front>
</TEI>
<affiliations><list><country><li>Australie</li>
<li>France</li>
<li>Royaume-Uni</li>
</country>
<region><li>Angleterre</li>
<li>Grand Londres</li>
</region>
<settlement><li>Londres</li>
</settlement>
</list>
<tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</region>
<name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name>
<name sortKey="Tischler, German" sort="Tischler, German" uniqKey="Tischler G" first="German" last="Tischler">German Tischler</name>
<name sortKey="Tischler, German" sort="Tischler, German" uniqKey="Tischler G" first="German" last="Tischler">German Tischler</name>
</country>
<country name="France"><noRegion><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name>
</noRegion>
</country>
<country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 007314 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 007314 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Asie
   |area=    AustralieFrV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:6FFE9D108EB5131A31FE0739DB1B421A603BECA1
   |texte=   Cover Array String Reconstruction
}}

This area was generated with Dilib version V0.6.33.
Data generation: Tue Dec 5 10:43:12 2017. Site generation: Tue Mar 5 14:07:20 2024

	Serveur d'exploration sur les relations entre la France et l'Australie
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur les relations entre la France et l'Australie

Cover Array String Reconstruction

Cover Array String Reconstruction

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri